#pragma once
#include<iostream>
#include<assert.h>

using namespace std;



namespace yangyi
{
	template <class K>
	struct BSTreeNode
	{
		K _key;
		BSTreeNode<K>* _left;
		BSTreeNode<K>* _right;

		BSTreeNode(const K& key)
			:_left(nullptr)
			,_right(nullptr)
			,_key(key)
		{

		}

		template <class K>
		class BSTree
		{
			typedef BSTreeNode<K> Node;
		public:
			BSTree(Node* root)
				:_root(root)
			{

			}
			BSTree(const BSTree<K>& bst)
			{

			}
			bool Insert(const K& key)
			{
				if (_root == nullptr)
					return false;
				Node* parent = nullptr;
				Node* cur = _root;
				while (cur)
				{
					if (cur->_key < key)
					{
						parent = cur;
						cur = cur->_right;
					}
					else if (cur->_key > key)
					{
						parent = cur;
						cur = cur->_left;
					}
					else
					{
						return false;
					}
				}
				cur = new Node(key);
				if (parent->_left == cur)
					parent->_left = cur;
				else
					parent->_right = cur;
				return true;
			}
			bool Erase(const K& key)
			{
				if (_root == nullptr)
					return false;
				Node* parent = nullptr;
				Node* cur = _root;
				while (cur)
				{
					if (cur->_key < key)
					{
						parent = cur;
						cur = cur->_right;
					}
					else if (cur->_key > key)
					{
						parent = cur;
						cur = cur->_left;
					}
					else
					{
						if (cur->_left == nullptr)
						{
							if (_root == cur)
							{
								_root = cur->_right;
							}
							else
							{
								if (parent->_left == cur)
								{
									parent->_left = cur->_right;
								}
								else
								{
									parent->_right = cur->_right;
								}
							}
							delete cur;
							cur = nullptr;
						}
						else if (cur->_right == nullptr)
						{
							if (_root == nullptr)
							{
								_root = cur->_left;
							}
							else
							{
								if (parent->_left == cur)
								{
									parent->_left = cur->_left;
								}
								else
								{
									parent->_right = cur->_left;
								}
							}
							delete cur;
							cur = nullptr;
						}
						else
						{
							Node* minparent = cur;
							Node* min = cur->_right;
							while (cur->_left)
							{
								minparent = min;
								min = min->_left;
							}
							::swap(min->_key, cur->_key);
							delete min;
						}
						return true;
					}
				}
				return false;
			}
			bool Find(const K& key)
			{
				if (_root == nullptr)
					return false;
				Node* cur = _root;
				while (cur)
				{
					if (cur->_key < key)
						cur = cur->_right;
					else if (cur->_key > key)
						cur = cur->_left;
					else
						return true;
				}
				return false;
			}
		private:
			Node* _Copy(Node* root)
			{
				if (root == nullptr)
					return nullptr;
				Node* copyRoot = new Node(root->_key);
				copyRoot->_left = _Copy(root->_left);
				copyRoot->_right = _Copy(root->_right);
				return copyRoot;
			}
			bool _EraseR(Node*& root, const K& key)
			{
				if (root == nullptr)
				{
					return false;
				}
				if (root->_key < key)
					return _EraseR(root->_right, key);
				else if (root->_key > key)
					return _EraseR(root->_left, key);
				else
				{
					Node* del = root;
					if (root->_left == nullptr)
						root = root->_right;
					else if (root->_right == nullptr)
						root = root->_left;
					else
					{
						Node* min = root;
						while (min->_left)
							min = min->_left;
						swap(min->_key, root->_key);
						return _EraseR(root->_right, key);
					}
					delete del;
					return true;
				}
			}
			bool _FindR(Node* root, const K& key)
			{
				if (root == nullptr)
					return false;
				if (root->_key < key)
					return _FindR(root->_right, key);
				else if (root->_key > key)
					return _FindR(root->_left, key);
				else
				{
					return true;
				}
			}
			bool _InsertR(Node*& root,const K& key)
			{
				if (root == nullptr)
				{
					root = new Node(key);
					return true;
				}
				if (root->_key < key)
					return _InsertR(root->_right, key);
				else if (root->_key > key)
					return _InsertR(root->_left, key);
				else
				{
					return false;
				}
			}
			void _InOrder(Node* root)
			{
				if (root == nullptr)
					return;
				_InOrder(root->_left);
				cout << root->_key << endl;
				_InOrder(root->_right);
			}
		private:
			Node* _root = nullptr;
		};
	};
}